package com.chengzhi.leetcode;


import java.util.*;
import java.util.stream.Collectors;

/**
 * @description: leet-code-array
 * @author: ruanchengzhi
 * @create: 2020-04-15 19:08
 **/
public class ArrayDemo {

    public static void main(String[] args) {
//        int[] nums = new int[]{4, 1, -1, 2, -1, 2, 3};
//        int[] ints = topKFrequent(nums, 2);
//        System.out.println(ints);
//        System.out.println(nums);
//        int[][] isConnected = new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//        System.out.println(findCircleNum(isConnected));
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7};
        rotate(nums, 3);
        System.out.println(nums);
    }

    /**
     * 189. 旋转数组
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     *
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }


    /**
     * 547. 省份数量
     * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
     * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
     * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
     * 返回矩阵中 省份 的数量。
     *
     * @param isConnected
     * @return
     */
    public static int findCircleNum(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] parent = new int[provinces];
        for (int i = 0; i < provinces; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < provinces; i++) {
            for (int j = i + 1; j < provinces; j++) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int circles = 0;
        for (int i = 0; i < provinces; i++) {
            if (parent[i] == i) {
                circles++;
            }
        }
        return circles;
    }

    public static void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

    public static int find(int[] parent, int index) {
        if (parent[index] != index) {
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }

    /**
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。在坐标内画 n 条垂直线，
     * 垂直线 i的两个端点分别为(i,ai) 和 (i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
     * <p>
     * 说明：你不能倾斜容器，且n的值至少为 2。
     *
     * @param height
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/10/16
     */
    public static int maxArea(int[] height) {
        int max = 0;
        for (int i = 0, j = height.length - 1; i < j; ) {
            int hg = height[i] < height[j] ? height[i++] : height[j--];
            max = Math.max(max, (j - i + 1) * hg);
        }
        return max;
    }

    /**
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     * @param nums
     * @param k
     * @return: int[]
     * @author: ruanchengzhi
     * @date: 2020/9/23
     */
    public static int[] topKFrequent(int[] nums, int k) {
        int length = nums.length;
        if (length == 0 || length < k) {
            return null;
        }
        Map<Integer, Integer> compareMap = new HashMap<>();
        for (int i = 0; i < length; i++) {
            compareMap.put(nums[i], compareMap.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(v -> v[1]));
        for (Map.Entry<Integer, Integer> entry : compareMap.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            if (pq.size() < k) {
                pq.add(new int[]{key, value});
            } else {
                if (pq.peek()[1] < value) {
                    pq.poll();
                    pq.offer(new int[]{key, value});
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = pq.poll()[0];
        }
        return ret;
    }

    /**
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     *
     * @param nums
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/8/7
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(nums.length, 1);
        for (int i = 0; i < nums.length; i++) {
            map.merge(nums[i], 1, (v1, v2) -> v1 + v2);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return 0;
    }


    public String minNumber(int[] nums) {
        List<String> list = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            list.add(String.valueOf(nums[i]));
        }
        return list.stream().sorted((o1, o2) -> (o1 + o2).compareTo(o2 + o1)).collect(Collectors.joining(""));
    }

    /**
     * 统计一个数字在排序数组中出现的次数。
     *
     * @param nums
     * @param target
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/8/6
     */
    public int search(int[] nums, int target) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result++;
            }
            if (nums[i] > target) {
                break;
            }
        }
        return result;
    }

    /**
     * 冒泡排序
     *
     * @param arr
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/6/1
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }

    /**
     * 二分查找
     *
     * @param array
     * @param value
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/6/1
     */
    public static int biSearch(int[] array, int value) {
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (array[mid] == value) {
                return mid + 1;
            }
            if (array[mid] < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }
        return -1;
    }

    /**
     * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
     *
     * @param nums
     * @return: int
     * @author: ruanchengzhim
     * @date: 2020/4/22
     */
    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.merge(nums[i], 1, Integer::sum);
        }
        int mid = nums.length / 2;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > mid) {
                return entry.getKey();
            }
        }
        return 0;
    }

    /**
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
     *
     * @param x
     * @param n
     * @return: double
     * @author: ruanchengzhi
     * @date: 2020/4/22
     */
    public static double myPow(double x, int n) {
        if (n < 0) {
            return 1 / power(x, -n);
        } else {
            return power(x, n);
        }
    }

    private static double power(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double v = power(x, n / 2);
        if (n % 2 == 0) {
            return v * v;
        } else {
            return v * v * x;
        }
    }


    /**
     * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
     * 使得a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     * <p>
     * 满足要求的三元组集合为：
     * [
     * [-1, 0, 1],
     * [-1, -1, 2]
     * ]
     *
     * @param nums
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     * @author: ruanchengzhi
     * @date: 2020/4/16
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> result = new HashSet<>();
        List<List<Integer>> lst = new ArrayList<>();
        if (nums.length < 3) {
            return lst;
        }
        Arrays.sort(nums);
        int startIndex, endIndex;
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            startIndex = i + 1;
            endIndex = nums.length - 1;
            while (startIndex < endIndex) {
                int sum = nums[startIndex] + nums[endIndex];
                if (i == startIndex || i == endIndex) {
                    break;
                }
                if (a + sum > 0) {
                    endIndex--;
                    continue;
                }
                if (a + sum < 0) {
                    startIndex++;
                    continue;
                }
                if (a + sum == 0) {
                    result.add(Arrays.asList(a, nums[startIndex], nums[endIndex]));
                    startIndex++;
                    continue;
                }
            }
        }
        lst.addAll(result);
        return lst;
    }

    /**
     * 两数只和
     *
     * @param nums   数组
     * @param target 目标值
     * @return: int[]
     * @author: ruanchengzhi
     * @date: 2020/4/17
     */
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[]{i, map.get(complement)};
            }
        }
        return null;
    }

    /**
     * 滑动窗口最大值
     * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
     * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     *
     * @param nums
     * @param k
     * @return: int[]
     * @author: ruanchengzhi
     * @date: 2020/4/15
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length <= 0) {
            return nums;
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //超出范围的去掉
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            //当前值大于之前的值，之前的不可能是最大值，可以删掉
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.add(i);
            if (i >= k - 1) {
                //此时开始是第一个滑动窗口
                res[i - k + 1] = nums[deque.peek()];
            }
        }
        return res;
    }


}
